红黑树
红黑树
是一种自平衡的平衡二叉树,是计算机科学中用到的一种数据结构。1972年,出现时,被称为平衡二叉B树,1978年被修改为如今的“红黑树”。
是一种特殊的二叉查找树,红黑树的每一个节点上都用存储位表示节点的颜色,每一个节点可以是红或黑;红黑树不是高度平衡的,他的平衡是通过“红黑规则”进行实现的。
红黑规则:
- 每一个节点或者是红色的,或者是黑色的。
- 根节点必须是黑色的
- 如果每一个节点没有子节点或者父节点,则该节点响应的指针属性值为Nil,这些Nil视为叶节点,每个叶节点(Nil)都是黑色的。
- 如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)
- 对每一个节点,从该节点到其所有后代叶节点的简单路径(不能回头,只能往前)上,均包含相同数目的黑色节点。
添加节点:
- 添加节点的颜色,可以是红色的,也可以是黑色的。
- 添加三个元素,默认颜色为黑色,一共需要调整两次
- 添加三个元素,默认颜色为红色,一共需要调整一次。所以,添加节点时,默认为红色,效率高
添加节点的小结:
添加节点默认是红色的。
flowchart LR A(添加节点)-->B(根节点位置)-->C(直接变成黑色) A-->D(非根节点位置)-->E(父节点为黑色) & F(父节点为红色) E-->G(则不需要任何操作) F-->H(叔叔节点为红色) & I(叔叔节点为黑色) H-->H1(1.将父节点设为黑色, 将叔叔节点设为黑色) H-->H2(2.将祖父节点设为红色) H-->H3(3.如果祖父节点为根节点, 则将根节点再次变为红色) I-->I1(1.将父节点设为黑色) I-->I2(2.将祖父节点设为红色) I-->I3(3.以祖父节点为支点进行旋转)